/*
    created: 2023/4/21  
    filename: threaded_btree.c
    author： 李东霖
    purpose: 线索二叉树的构建实现
*/

#include "threaded_btree.h"



int CreateBTree(TBTTree * tree, char * str)
{
    if(*tree != NULL || str == NULL) return -1; 
    TBTNode* p;
    int k;
    //写一个简易的栈  
    TBTNode* stack[MAXSIZE];
    int top = -1;
    int pos = 0;
    char *ch = str;
    while(*ch != '\0')
    {
        switch (*ch)
        {
            //遇到左括号，说明下一个是他的左孩子 把他进栈
        case '(':
        {
            ++top;
            stack[top] = p;
            k = 1;
            break;
        }
        //当前结点的左右都已经处理完了，该结点退栈
        case ')':
        {
            --top;
            break;
        }
        //下一个是这一层的兄弟结点，改变k值
        case ',':
        {
            k = 2;
            break;
        }   
        default:
        {
            p = (TBTNode*)malloc(sizeof(TBTNode));
            p->data = *ch;
            p->lchild = p->rchild = NULL;
            p->ltag = p->rtag = 0;
            if(*tree == NULL)*tree = p;
            else
            {
                switch(k)
                {
                    case 1:stack[top]->lchild = p;break;
                    case 2:stack[top]->rchild = p;break;
                }
            }
            break;
        }
            
        }
    ++ch;
    }
    return 0;
}

//中序遍历  
void InOrder(TBTTree tree)
{
    if(tree == NULL) return;
    
    InOrder(tree->lchild);
    printf("%c",tree->data);
    InOrder(tree->rchild);
}

// 中序遍历二叉树线索化主函数。
void CreateInThread(TBTTree tree)
{
    if(tree == NULL) return;
    TBTNode *pre = NULL;
    //递归处理线索化
    InThread(tree,&pre);
    //处理最后一个结点
    pre->rtag = 1;
    pre->rchild = NULL;
}


//中序遍历线索化二叉树的递归函数，参数pp是当前节点，pre是前驱结点。
void InThread(TBTTree tree, TBTNode **pre)
{
    if(tree == NULL)return;
    //递归线索化左子树
    InThread(tree->lchild,pre);
    if(tree->lchild == NULL)
    {
        tree->lchild = *pre;
        tree->ltag = 1;
    }
    printf("%c",tree->data);
    //处理前驱结点的后继线索
    if((*pre) != NULL && (*pre)->rchild == NULL)
    {
        (*pre)->rchild = tree;
        (*pre)->rtag = 1;
    }
    //修改前驱
    (*pre) = tree;
    //递归线索化右子树
    InThread(tree->rchild,pre);
}

//正向输出中序线索化过的二叉树
void CInOrder(TBTTree tree)
{
    if(tree == NULL)return;
    TBTNode* p = tree;
    //找到他的起始结点
    while(p->ltag == 0)
    {
        p = p->lchild;
    }

    //开始遍历
    while(p != NULL)
    {
        printf("%c",p->data);
        //线索化过
        if(p->rtag == 1)
        {
            p = p->rchild;
        }
        //没有线索化 找他的右子树的最左结点
        else
        {
            p = p->rchild;
            while(p->ltag == 0)
            {
                p = p->lchild;
            }
        }
    }
}




//反向输出中序线索化过的二叉树
void RInOrder(TBTTree tree)
{
    if(tree == NULL)return;
    TBTNode* p = tree;
    //找到他的起始结点
    while(p->rtag == 0)
    {
        p = p->rchild;
    }

    //开始遍历
    while(p != NULL)
    {
        printf("%c",p->data);
        //线索化过
        if(p->ltag == 1)
        {
            p = p->lchild;
        }
        //没有线索化 找他的左子树的最右结点
        else
        {
            p = p->lchild;
            while(p->rtag == 0)
            {
                p = p->rchild;
            }
        }
    }

}